package leetcode.LinkedList;

import java.util.*;

/**
 * @author wangmaolin1
 * @date 2021/12/11 下午11:39
 */
public class _30串联所有单词的子串 {

    /**
     * left=0 target = -1;target 为第一次匹配到的 words 子串的长度 count=0 匹配次数 1.先从s 的left索引开始找到一个words 子串，记录起始位置
     * left1，left=left1,target=匹配到的子串索引，count=1 2.然后从 left+1开始寻找剩下的子串，记录起始位置 left2，count=2 2.1 如果 left2>left1+1，则
     * left=left2 2.2否则 left不变 3.然后从 left2+1开始寻找剩下的子串，更新 left，当count= words.length 次时，记录此时的 left
     * <p>
     * 然后 left+=words[target].length，记录重复1，直到 left>s.length-words.length+1
     *
     * @param s
     * @param words
     * @return
     */
    public static List<Integer> findSubstring(String s, String[] words) {
        if (s == null || s.length() == 0) {
            return new ArrayList<>();
        }
        List<Integer> result = new ArrayList<>();
        int left = 0;
        int target = -1;
        int count = 0;
        //key：第 i 个 word 的首字母，value:i
        Map<Character, List<Integer>> wordHeadMap = new HashMap<>(words.length);
        for (int i = 0; i < words.length; i++) {
            int finalI1 = i;
            wordHeadMap.computeIfPresent(words[i].charAt(0), (k, v) -> {
                v.add(finalI1);
                return v;
            });
        }
        while (left <= s.length() - words.length + 1) {
            Set<Integer> set = new HashSet<>();
            int tempLeft = left;
            for (int i = tempLeft; set.size() < words.length && i < s.length(); ) {
                if (!wordHeadMap.containsKey(s.charAt(i))) {
                    i++;
                    left = i;

                    set.clear();
                    continue;
                }
                List<Integer> indexList = wordHeadMap.get(s.charAt(i));
                if (indexList == null) {
                    //如果没有子串的首字母与该字符相等，直接进入下个循环
                    i++;
                    left = i;

                    set.clear();
                    continue;
                }
                //TODO
                Integer targetWordIndex =0;
                int findCount=0;
                for (Integer integer : indexList) {
                    if (set.contains(integer)){
                        findCount++;
                    }
                }
                if (findCount==indexList.size()){
                    //所有该子串已经包含了
                    i++;
                    left=i;
                    continue;
                }
                if (set.contains(indexList)) {
                    //如果有相等的子串，但是已经匹配过了，则继续下一个循环
                    set.clear();
                }

                //待匹配的子串,从 i 开始匹配 word
                String word = words[targetWordIndex];
                boolean match = false;
                for (int j = i + 1; j < s.length(); j++) {
                    if (s.charAt(j) == word.charAt(j - i)) {
                        if ((j - i + 1) == word.length()) {
                            match = true;
                            break;
                        }
                    } else {
                        break;
                    }
                }
                if (match) {
                    //当前索引的 word 子串匹配到了
                    set.add(targetWordIndex);
                    //下次从该word 后面一个位置开始匹配下一个单词
                    tempLeft = i + word.length();

                    if (set.size() == 1) {
                        left = tempLeft;
                        target = i;
                    }
                    i = tempLeft;
                    if (i >= s.length()) {
                        break;
                    }


                } else {
                    i++;
                    left = i;

                }

            }
            if (set.size() == words.length) {
                //匹配到了所有 words 子串
                result.add(target);

            }

        }
        return result;

    }

    public static void main(String[] args) {
        //"barfoofoobarthefoobarman"
        //["bar","foo","the"]
        System.out.println(findSubstring("barfoofoobarthefoobarman", new String[]{"bar", "foo", "the"}));
    }

}
